package leetcode.hot100;

/**
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）
 * 必须原地修改，只允许使用额外常数空间
 */
@SuppressWarnings("all")
public class _31_下一个排列 {

    /**
     * 输入：nums = [1,2,3]
     * 输出：[1,3,2]
     * 输入：nums = [3,2,1]
     * 输出：[1,2,3]
     */
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        // 从后往前找到第一个降序的数，比如1，2，3 --- 第一个降序的数为2
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // 如果是3，2，1 --- i遍历结束为-1
        if (i >= 0) {
            // 有降序的数存在，如 4,5,2,6,3,1，找到2
            int j = nums.length - 1;
            // 从后往前找到比2大的第一个数3，并和3交换位置
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            // 如果i<0，那么最大数反转就是最小数 321---》123
            // 4,5,2,6,3,1---》4,5,3,6,2,1
            swap(nums, i, j);
        }
        // 4,5,2,6,3,1 ---》4,5,2,1,3,6 ---》从后往前3的右边由整体升序变为降序
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 将[start,nums.length-1]区间范围内的数两两交换
     */
    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}
